Suppose each edge of a simple connected undirected graph is given a unique number from the numbers $1, 2, \dots, $q$, where $q$ is the number of edges of that graph. Then each vertex is labelled with sum of the labels of the edges incident to it. If no two vertices have the same label, then the graph is called an antimagic graph. We prove that the Cartesian product of wheel graph and path graph is antimagic.

In this paper, we find the star chromatic number of central graph of complete bipartite graph and corona graph of complete graph with path and cycle.

This paper represents a technique for finding optimal paths with multiple indexes in a graph. Up to the present time, all optimal paths have been determined upon one index, say, distance for which an evaluation method exists. In this paper firstly we define multiple indexes for each edge in such a way that anyone can treat the factor for assigning an optimal path. Here, we use Data Envelopment Analysis (DEA) technique for designing a model that can identify optimal paths with multiple indexes, and separate them from the other paths.

In recent decades, in view of the widespread use of graph data in different applications, for instance in social networks, communications networks, etc. many researchers have investigated different anonymization approaches for such data. Although relational data anonymization is mature enough, graph data anonymization is a challenging and relatively new field of research. One of the most important anonymization models against identity disclosure risk in graph data addresses the number of links a node’ s neighbors have, in the graph. In this paper, an improved method is proposed that realizes this model using both edge addition and deletion to the original graph. The application of the method to a number of different real-world graphs confirms that the method can produce more useful graphs in terms of one of the most important characteristics in such data, i. e., the Average Path Length in the graph and graph structure will undergo less change.

Let $G$ be a $(p,q)$ graph. Let $V$ be an inner product space with basis $S$. We denote the inner product of the vectors $\omega_{1}$ and $\omega_{2}$ by $<\omega_{1},\omega_{2}>$. Let $\chi: V(G) \rightarrow S$ be a function. For edge $uv$ assign the label $<\chi(u),\chi(v)>$. Then $\chi$ is called a vector basis $S$-cordial labeling of $G$ if $|\chi_{\omega_{1}}-\chi_{\omega_{2}}|\leq 1$ and $|\delta_i-\delta_j |\leq 1$ where $\chi_{\omega_{i}}$ denotes the number of vertices labeled with the vector $\omega_{i}$ and $\delta_i$ denotes the number of edges labeled with the scalar $i$. A graph which admits a vector basis $S$-cordial labeling is called a vector basis $S$-cordial graph . In this paper, we prove that the graphs $L_{n}\odot mK_{1}$ and $T(P_{n})\odot mK_{1}$ are the vector basis $\{(1,1,1,1), (1,1,1,0), (1,1,0,0), (1,0,0,0)\}$-cordial.

Please click on PDF to view the abstract

The independence graph Ind(G) of a graph G is the graph with vertices as maximum independent sets of G and two vertices are adjacent, if and only if the corresponding maximum independent sets are disjoint. In this work, we find the independence graph of Cartesian product of d copies of complete graphs Kq, which is known as the Hamming graph H(d, q). Greenwell and Lovasz [7] found that the independence number of direct product of d copies of Kq as qd−1. We prove that the independence number of Hamming graph H(d, q), which is cartesian product of d copies of Kq, is also qd−1. As an application of our findings, we find answers for rook problem in higher dimensional square chess board.